1. Field of the Invention
The present invention relates to the field of digital system simulation, and more specifically, to simulating non-binary digital systems, defined as digital systems wherein input and output signals can have more than two defined logical states. In particular, the present invention provides an efficient methodology and environment for simulating digital systems designed in the N-nary logic design style.
2. Description of the Related Art
N-NARY logic is a new dynamic logic design style fully described in a copending patent application, U.S. patent application Ser. No. 09/019,355, filed Feb. 5, 1998, now U.S. Pat. No. 6,066,965, and titled xe2x80x9cMethod and Apparatus for a N-Nary logic Circuit Using 1-of-4 Signalsxe2x80x9d, which is incorporated herein for all purposes and is hereinafter referred to as xe2x80x9cThe N-nary Patent.xe2x80x9d
Supporting a new logic design style requires the invention of new design support techniques and tools to facilitate the computer-aided design and analysis of logic circuits and their constituent subcircuits. The N-NARY logic design style is no exception. For example, the following copending patent applications, incorporated herein for all purposes, disclose a computer-aided design methodology and tool, and an associated hardware description language suitable for use by designers employing the N-NARY logic design style:
These applications are collectively referred to hereinafter as xe2x80x9cThe N-nary Design Tools Patents.xe2x80x9d
The N-nary Design Tools Patents disclose a methodology and apparatus for describing and developing the physical design and interconnectivity of N-nary gates and circuits. As described in the N-nary Design Tools Patents, a designer developing a logic circuit in the N-nary logic style produces a syntax statement, preferably encoded in a combination of ANSI C and the N-nary C language disclosed in U.S. patent application Ser. No. 09/210,408. This syntax statement describes both the logical function implemented by the logic circuit being designed and the specific configuration of transistors required to build said circuit. As described in detail in the N-nary Design Tools Patents, the design tool disclosed therein compiles the syntax statement and generates both a behavioral model, which is a software-implemented simulation of the logic circuit under design, and a schematic, which is a physical description of the logic circuit under design. The focus of the present invention is on the content and use of the behavioral model that is an output of the design tool.
As semiconductors have become more and more advanced, with increasingly complex levels of integration, semiconductor designers have come to rely upon the use of software behavioral models to simulate and verify circuits under design as an important part of the design process. Commercially-available proprietary logic simulation tools have been developed to support this verification effort. These simulators operate on a behavioral model of a circuit under design by providing simulated inputs having various characteristics, and determining the associated outputs.
The simplest logic simulators in use today for binary-based designs are two-state models, meaning that they model only the two valid logical states of binary wires and gates (either a 1 or a 0). More sophisticated models also account for a number of other possible states of the wires and gates in a binary design. Three-state models provide for both valid logical states, plus the uninitialized state (i.e., possible states in a three-state model are 1, 0, and X). This is a popular extension because it may allow designers to simplify the hardware of complex designs by eliminating power-on reset functions in as much of the logic as possible. A three-state simulation allows the designer to ensure that no operation depends upon a gate output until that gate output is loaded from a valid, defined source.
Four-state models add the xe2x80x9cundrivenxe2x80x9d or high-impedance state (commonly designated xe2x80x9cZxe2x80x9d). This is particularly useful for wires that can be driven from more than one location. Only one driver is allowed to drive the wire at a time, with the remainder being put into a high impedance state. The value of the wire is determined by finding a driver in the low impedance state and selecting its output value.
There are a variety of extensions beyond the four-state model where the degree to which the driver is being driven is included for each possible logical value. For example, a simple nine-state model extends the four-state model by replacing the Z state with the S, R and Z state modifiers, or strengths. The S state indicates the value is driven xe2x80x9cstrongxe2x80x9d, usually by having an ON transistor connected to the appropriate power or ground plane. The R state indicates that the value is driven xe2x80x9cweakxe2x80x9d, usually by having a resistor (often constructed from a properly biased transistor) connected to the appropriate power or ground plane. The Z state indicates the wire is not driven, but the value which last appeared on the wire is included. In this way, the wire is modeled as a capacitor which retains its value. A popular variation of the simple nine-state simulator provides for strong and resistive versions of the 0, 1 and X states, along with high-impedance, undefined and uninitialized states, all without regard to the boolean value which last appeared on the wire.
Finally, the twelve-state model extends the simple nine-state model by providing for indeterminate versions of the 0, 1, and X states.
Table 1 provides a summary of the logic states supported by existing simulation tools currently used to evaluate and verify typical binary-based logic designs.
Designers have found that while extended-state logic simulation on a computer workstation is a powerful verification tool, it is expensive in terms of the time required to compute the various possible outputs of the design under verification, and in terms of the memory capacity required by the verification system. The overall simulation time is sensitive to the amount of memory used by the simulation as well as the number of individual discrete components of the design to be simulated. The more logic that is being simulated, the more memory that is used. This invention helps to limit the amount of computations and memory required for simulating N-Nary designs which thereby improves performance of the simulation.
To model all possible inputs of a design and determine the output of the design, state-based models commonly use truth tables that correspond to the boolean equation or logic function that the design implements. Assuming that a gate simulation truth table contains an entry for every combination of the gate""s inputs and outputs, the size of the truth table is determined by the equation
N=(x-state)(I+o)
where
N=the number of entries in the truth table;
x-state=the number of states to be modeled;
I=the number of possible inputs to the gate;
o=the number of possible outputs to the gate.
Applying this equation, we see that using a 4-state model to analyze a gate with a total often inputs and outputs would require a truth table with 1024K entries, corresponding to 1024 Kbytes of memory. Adding two more input or output pins to the gate would increase the size of the truth table to 6384K. As these examples demonstrate, modeling complex binary gates using extended-state modeling on a typical computer workstation quickly becomes impractical, due to memory limitations. Designers working in this area have developed a number of work around solutions, such as mapping large truth table function to multiple smaller truth table functions, or ignoring certain states within a multiple-state model for certain designs, to decrease the size of the relevant truth table. Nevertheless, these work around solutions are less than ideal, and negatively impact the capability of the verification tool and the performance of the simulation itself.
Although these logic simulator tools support multiple states within a design, they were designed for and are most applicable to binary logic. The various states modeled generally relate only to initialization or drive strength, and the only two valid functional values are logical 0 and logical 1. Attempting to use any of these modeling tools to verify a non-binary N-nary design is complicated and inefficient.
The N-nary logic family supports a variety of signal encodings. All signals in N-nary logic are of the 1-of-N form where N is any integer greater than one. In N-nary logic, a bundle or group of N wires are used to indicate one of N possible signal values. The signal value is determined by which one of the N wires within the bundle is asserted (logical 1). Table 2 demonstrates, using a 1-of-4 N-nary signal as an example, the correlation between the N-nary signal value (in Table 2, decimal values 0-3) and which of the N wires that comprise the N-nary signal (wires A[3] through A[0]) is asserted.
As shown in Table 2, and described further in the N-nary Patent, more than one wire will never be asserted for a valid 1-of-N signal. Similarly, N-nary logic generally requires that a high voltage be asserted on only one wire for all values, even 0. (Some versions of N-nary logic allow for a valid N-nary xe2x80x9cnullxe2x80x9d signal, where a high voltage is not asserted on any wire. In these versions, a valid xe2x80x9cnullxe2x80x9d signal is a signal that has not yet evaluated and whose value is not required to accomplish a given function.) In versions that do not support a xe2x80x9cnullxe2x80x9d signal, an N-nary signal that does not have a high voltage asserted on any wire is considered to be an invalid signal.
As Table 2 illustrates, N-nary logic design differs from binary logic in that there is a distinction between an N-nary wire and an N-nary signal. While N-nary signals are not limited to binary values (an N-nary signal can have N possible values), each wire of an N-nary signal can be considered to be binary, in that its functional value can only be either 0 or 1.
Any one N-nary logic gate may comprise multiple input N-nary signals and/or multiple output N-nary signals. In such a case, a variety of different N-nary signal encodings may be employed. For instance, N-nary design principles would support a gate that comprises two inputs and two outputs, where the inputs are a 1-of-4 signal and a 1-of-2 signal and the outputs are a 1-of-4 signal and 1-of-3 signal. This gate could be verified using one of the traditional binary verification tools discussed above, applied at the N-nary wire (rather than N-nary signal) level. However, this gate""s input and output wires total 13. Even a 4-level simulation would require a truth table with 67,109K entries. As this example demonstrates, attempting to simulate even a few N-nary gates at this level would be far too expensive, both in terms of computation time and local workstation cache memory capacity. Therefore, a new simulation tool and methodology enabling designers working in the N-nary logic design style to properly and efficiently verify their designs is required.
The present invention comprises a method of efficiently simulating logic designs comprising signals that are capable of having more than two unique decimal values and multiple unique drive states, such as designs based upon the new N-nary logic design style. The present invention models N-nary signals in a specific format comprising a signal value field that holds the signal""s unique decimal value, a signal strength field that conveys the signal""s drive state, and a signal definition field that conveys whether the signal is a defined or an undefined signal. The unique decimal value of defined signals occupies the least significant bits in the model, thus allowing the simulator to perform mathematical and logical operations on the gate""s input and output signals at the signal value level, rather than at the wire/bit level.
The simulator, sometimes also referred to herein as a behavioral model, comprises an executable software-implemented simulation model that is compiled from a gate syntax statement and one or more simulation environment files. The simulator generally comprises a plurality of instructions wherein the decimal values of a gate""s input logic signals, modeled in accordance with the conventions described above, are determined and mathematically or logically manipulated to obtain the decimal value of each of the gate""s one or more output logic signals. Simulating gates such as adders, buffers, and multiplexers by mathematically and/or logically manipulating the decimal values of the gates"" input and output signals is a much more efficient approach than traditional binary-based simulation techniques, where simulation of these kinds of gates can require complex truth tables as described above, and/or breaking the gate down into its primitive logic components.
The simulator of the present invention comprises an input logic signal model reader that determines the unique decimal value of the gate""s modeled input signals that are defined signals, an arithmetic/logical operator that mathematically and/or logically manipulates the decimal values of the gate""s input signals to obtain the decimal value of the gate""s output signals, an output logic signal model generator that generates a signal model for each of the output logic signals determined by the arithmetic/logical operator, and an output message generator that generates one or more output messages that pack relevant simulation data into a format optimized for the architecture of the simulation host. In a preferred embodiment, each output message is output- or input-signal-specific, and includes the following information corresponding to a specific input or output logic signal of the gate being simulated: current (or last) unique decimal value, maximum unique decimal value possible, bit mask indicating unique decimal values held thus far, null value propagation possible, and number of times null value has been propagated.